import java.util.*;

// 力扣12.整数转罗马数字
class Solution {
    public String intToRoman(int num) {
        // 使用TreeMap保持有序性，方便从大到小遍历
        TreeMap<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");

        StringBuilder sb = new StringBuilder();

        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            int value = entry.getKey();
            String symbol = entry.getValue();

            // 当当前数值大于等于映射表中的值时，添加对应的罗马字符
            while (num >= value) {
                sb.append(symbol);
                num -= value;
            }
        }

        return sb.toString();
    }
}


// 力扣14. 最长公共前缀
class Solution1 {
    public String longestCommonPrefix(String[] strs) {
        String s = strs[0];
        for(int i=1;i<strs.length;i++){
            int k = 0;
            StringBuilder temp = new StringBuilder();
            while(k < strs[i].length() && k < s.length()){
                if(k == 0&&s.charAt(k) != strs[i].charAt(k)){
                    return "";
                }
                if(s.charAt(k) != strs[i].charAt(k)){
                    break;
                }
                temp.append(strs[i].charAt(k));
                k++;
            }
            s = temp.toString();
        }
        return s;
    }
}

// 力扣151. 反转字符串中的单词
class Solution2 {
    public String reverseWords(String s) {
        s = s.trim();
        ArrayList<String> str = new ArrayList<>();
        int k = s.length()-1;
        while(k>=0){
            int old = k;
            while(k>=0&&s.charAt(k)!=' '){
                k--;
            }
            str.add(s.substring(k+1,old+1));
            while(k>=0&&s.charAt(k)==' '){
                k--;
            }

        }

        StringBuilder ans = new StringBuilder();
        for(int i=0;i<str.size();i++){
            if(i == str.size()-1){
                ans.append(str.get(i));
                break;
            }
            ans.append(str.get(i) + " ");
        }
        return ans.toString();
    }
}

// 力扣6. Z 字形变换
class Solution3 {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;  // 特殊处理numRows=1的情况

        int n = (numRows - 1) * 2;
        StringBuilder ans = new StringBuilder();

        for (int i = 0; i < numRows; i++) {
            int left = i * 2;
            int right = n - left;
            ans.append(getRowChars(i, left, right, s));
        }
        return ans.toString();
    }

    private String getRowChars(int start, int step1, int step2, String s) {
        StringBuilder res = new StringBuilder();
        int pos = start;
        boolean useStep2 = true;  // 初始使用step2

        while (pos < s.length()) {
            res.append(s.charAt(pos));

            // 处理第一行和最后一行的情况
            if (step1 == 0 || step2 == 0) {
                pos += (step1 == 0 ? step2 : step1);
            } else {
                // 交替使用两个步长
                pos += (useStep2 ? step2 : step1);
                useStep2 = !useStep2;
            }
        }
        return res.toString();
    }
}


// 力扣28. 找出字符串中第一个匹配项的下标
class Solution4 {
    public int strStr(String haystack, String needle) {
        char[] ch1 = haystack.toCharArray();
        char[] ch2 = needle.toCharArray();
        if(ch2.length>ch1.length){
            return -1;
        }
        for(int start = 0;start<haystack.length();start++){
            if(haystack.length()-start < needle.length()){
                return -1;
            }
            if(ch1[start] == ch2[0] && isValid(start,ch1,ch2)){
                return start;
            }
        }
        return -1;
    }
    public boolean isValid(int start,char[] ch1,char[] ch2){
        int k = 0;
        while(k<ch2.length){
            if(ch1[start]!=ch2[k]){
                return false;
            }
            start++;
            k++;
        }
        return true;
    }
}